/*
 * BranchAndBound.java
 *
 * $LastChangedDate$
 * $LastChangedRevision$
 * Vicente J. Ferrer Dalmau
 * < vicente@jdalmau.es >
 *
 * Implementation of the branch and bound search algorithm.
 */

package com.carpool;

import java.util.ArrayList;

/**
 *
 * @author Vicente J. Ferrer Dalmau
 */
public class BranchAndBound {

	RoutesMatrix distances;
	int sourceCity;
	int destinationCity;
	String result = new String();

	@SuppressWarnings("rawtypes")
	ArrayList initialRoute, optimumRoute;
	int nodes = 0;
	int routeCost = 0;
	int optimumCost = Integer.MAX_VALUE;    

	public BranchAndBound(RoutesMatrix matrix, int sourceCity, int destinationCity) {
		distances = matrix;
		this.sourceCity = sourceCity;
		this.destinationCity = destinationCity;

	}
	
	@SuppressWarnings("rawtypes")
	public float getDistance(ArrayList list) {
		float distance = 0;
		for (int i=0; i<list.size()-1; i++) {
			distance += distances.getCost(list.indexOf(i), list.indexOf(i+1));
		}
		return distance;
		
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public String execute () {

		initialRoute = new ArrayList();
		initialRoute.add(sourceCity);
		optimumRoute = new ArrayList();
		nodes++;
		search(sourceCity, initialRoute, destinationCity);
		return result;         
	}


	/**
	 * @param from node where we start the search.
	 * @param route followed route for arriving to node "from".
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public void search (int from, ArrayList followedRoute, int destination) {
		if (followedRoute.size() == (distances.getCitiesCount()-1)) {
			followedRoute.add(destination);
			nodes++;
			routeCost += distances.getCost(from, destination);
			if (routeCost < optimumCost) {
				optimumCost = routeCost;
				optimumRoute = (ArrayList)followedRoute.clone();
			}
			routeCost -= distances.getCost(from, destination);
		}
		else {
			for (int to=0; to<distances.getCitiesCount(); to++){
				if (!followedRoute.contains(to) && to!=destination) {
					routeCost += distances.getCost(from, to);
					if (routeCost < optimumCost) { 
						ArrayList increasedRoute = (ArrayList)followedRoute.clone();
						increasedRoute.add(to);
						nodes++;
						search(to, increasedRoute, destination);    
					}
					routeCost -= distances.getCost(from, to);
				}
			}
		}        
	}

}
